package euler.p051_100;

import euler.MainEuler;

public class Euler085 extends MainEuler {

    /*
        By counting carefully it can be seen that a rectangular grid
        measuring 3 by 2 contains eighteen rectangles.

        Although there exists no rectangular grid that
        contains exactly two million rectangles,
        find the area of the grid with the nearest solution.
     */
    public String resolve() {
        int bestRows = 0;
        int bestColumns = 0;
        int bestSolution = 0;

        int target = 2000000;

        // 2000 * (2000 + 1) > target * 2

        for (int rows = 3; rows <= 2000; rows++) {
            for (int columns = rows; columns > 0 ; columns--) {
                int rectangles = 0;
                boolean terminar = false;

                for (int i = 1; !terminar && i <= rows; i++) {
                    for (int j = 1; !terminar && j <= columns; j++) {
                        rectangles+=((rows - i + 1) * (columns - j + 1));
                        if (rectangles > target && i!=rows && j!=columns) {
                            terminar = true;
                        }
                    }
                }

                if (terminar) {
                    continue;
                }

                if (Math.max(target, bestSolution) - Math.min(target, bestSolution) >
                Math.max(target, rectangles) - Math.min(target, rectangles)) {
                    bestRows = rows;
                    bestColumns = columns;
                    bestSolution = rectangles;
                } else if (target > rectangles){
                    break;
                }
            }
        }

        return String.valueOf(bestRows * bestColumns);
    }

}
